package hihocode;

import java.util.Scanner;

public class Heap {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n;
		int[] heap;
		while(scanner.hasNext()){
			n = scanner.nextInt();
			heap = new int[n];
			int index = 0;
			for(int i = 0; i < n; i++){
				
				if(scanner.next().charAt(0) == 'A'){
					int next = scanner.nextInt();
					heap[index] = next;
					heapAdjustBottom(heap, index++, 0);
				}else{
					System.out.println(heap[0]);
					heap[0] = 0;
					heapAdjustTop(heap, 0, index--);
				}
				
				for(int j = 0; j < n; j++){
					System.out.print(heap[j] + "  ");
				}
				System.out.println();
			}
		}
		scanner.close();
	}
	
	public static void heapAdjustTop(int[] heap, int i, int toIndex){
		int maxIndex = i;
		int leftIndex = i * 2 + 1;
		int rightIndex = i * 2 + 2;
		if(i < (toIndex + 1) / 2){
			if(leftIndex <= toIndex && heap[leftIndex] > heap[maxIndex]){
				maxIndex = leftIndex;
			}
			if(rightIndex < toIndex && heap[rightIndex] > heap[maxIndex]){
				maxIndex = rightIndex;
			}
			if(maxIndex != i){
				swap(heap, maxIndex, i);
				heapAdjustTop(heap, maxIndex, toIndex);
			}
		}
	}
	
	public static void heapAdjustBottom(int[] heap, int i, int toIndex){
		if(i == toIndex){
			return;
		}
		int maxIndex = i;
		int parent = (i - 1) / 2;
		if(parent >= toIndex){
			if(heap[parent] > heap[maxIndex]){
				maxIndex = parent;
			}
			if(maxIndex == i){
				swap(heap, parent, i);
				heapAdjustBottom(heap, parent, toIndex);
			}
		}
	}
	
	public static void swap(int[] nums, int i, int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}
